package com.banmao.algorithm.No201To300.No235;

public class Solution1 {

    int max, min;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(q.val > p.val) {
            max = q.val;
            min = p.val;
        } else {
            max = p.val;
            min = q.val;
        }

        TreeNode res = recursive(root);

        return res;
    }

    private TreeNode recursive(TreeNode root) {

        // 中序遍历
        if(root == null) {
            return null;
        }

        // 二叉搜索树的特性是节点的左子树一定小于节点，右子树反之
        if(root.val < max && root.val > min) {
            return root;
        } else if((root.val == max && root.val > min) || (root.val == min && root.val < max)) {
            return root;
        } else {
            TreeNode left = recursive(root.left);
            if(left != null) {
                return left;
            } else {
                TreeNode right = recursive(root.right);
                return right;
            }
        }

    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
    TreeNode(int x, TreeNode left, TreeNode right) {
        this.val = x;
        this.left = left;
        this.right = right;
    }
}
